#include "QuadTree.h"

CQuadTree::CQuadTree(int w, int h)
{
	m_nMapWidth = w;
	m_nMapHeight = h;
	m_qRoot = new QuadNode (0, 0, m_nMapWidth, m_nMapHeight);
}
CQuadTree::~CQuadTree()
{
	m_qRoot = NULL;
}

void CQuadTree::addObj(QuadNode* _root, Object* _reb)
{
	
	if (_root != NULL)
	{
		//0: Add | 1: Left_Top | 2: Right_Top | 3: Left_Bottom | 4: Right_Bottom
		int result = 0;

		int ObjectWidth = _reb->m_ObRect->right - _reb->m_ObRect->left;
		int ObjectHeight = _reb->m_ObRect->bottom - _reb->m_ObRect->top;

		int MapWidth = _root->m_Rect->right - _root->m_Rect->left;
		int MapHeight = _root->m_Rect->bottom - _root->m_Rect->top;

		int MapWidthNew = ( _root->m_Rect->right + _root->m_Rect->left ) / 2;
		int MapHeightNew = ( _root->m_Rect->bottom + _root->m_Rect->top ) / 2;
		/*char str[25];
		itoa(MapWidth, str, 10);
		MessageBox(NULL, str , "Error", MB_OK);*/

		if ((ObjectWidth*ObjectHeight > MapWidth*MapHeight/4)||
			(MapWidthNew > _reb->m_ObRect->left && MapWidthNew <= _reb->m_ObRect->right)||
			(MapHeightNew > _reb->m_ObRect->top && MapHeightNew <= _reb->m_ObRect->bottom))
		{
			result = 0;
		}
		else
		{
			//find LT
			if (_reb->m_ObRect->left >= _root->m_Rect->left &&
				_reb->m_ObRect->left < MapWidthNew &&
				_reb->m_ObRect->top >= _root->m_Rect->top&&
				_reb->m_ObRect->top < MapHeightNew)
			{
				result = 1;
			}
			else//find RT
				if(_reb->m_ObRect->left < _root->m_Rect->right &&
					_reb->m_ObRect->left >= MapWidthNew &&
					_reb->m_ObRect->top >= _root->m_Rect->top&&
					_reb->m_ObRect->top < MapHeightNew)
					result = 2;
			else//find LB
				if(_reb->m_ObRect->left >= _root->m_Rect->left&&
				_reb->m_ObRect->left < MapWidthNew &&
				_reb->m_ObRect->top < _root->m_Rect->bottom&&
				_reb->m_ObRect->top >= MapHeightNew)
				result = 3;
			else// find RB
				result = 4;
		}

		//Add object
		if(result == 0)
		{
			_root->ListObj.push_back(_reb);
			m_nCount++;
			//MessageBox(NULL, "success" , "Error", MB_OK);
		}
		else
		{
			if (MapWidth/2 > LIMIT_W_H && MapHeight/2 > LIMIT_W_H)
			{
				switch(result)
				{
				case 1://left_top
					if(_root->LT == NULL)
						_root->LT = new QuadNode(_root->m_Rect->left, _root->m_Rect->top, MapWidth / 2, MapHeight / 2);
					addObj(_root->LT, _reb);
					break;
				case 2://right top
					if(_root->RT == NULL)
						_root->RT = new QuadNode(MapWidthNew, _root->m_Rect->top, MapWidth / 2, MapHeight / 2);
					addObj(_root->RT, _reb);
					break;
				case 3://left bottom
					if(_root->LB == NULL)
						_root->LB = new QuadNode(_root->m_Rect->left, MapHeightNew, MapWidth / 2, MapHeight / 2);
					addObj(_root->LB, _reb);
					break;
				case 4://right bottom
					if(_root->RB == NULL)
						_root->RB = new QuadNode(MapWidthNew, MapHeightNew, MapWidth / 2, MapHeight / 2);
					addObj(_root->RB, _reb);
					break;
				}
			}
		}
	}
}

void CQuadTree::getObjInRect(QuadNode* root, RECT Screen, vector<Object*>& result)
{
	//int n = result.size();
	/*char str[25];
	itoa(Screen.bottom, str, 10);
	MessageBox(NULL, str , "Error", MB_OK);*/
	RECT rec;
	for ( int i = 0; i < root->ListObj.size(); i++)
	{
		if ( IntersectRect( &rec, root->ListObj[i]->m_ObRect, &Screen)!= 0 )
		{
			if (IntersectRect(&rec, root->m_Rect, root->ListObj[i]->m_ObRect) == 0)
			{
				Object* obj = root->ListObj[i];
				root->ListObj.erase(root->ListObj.begin() + i);
				i--;
				this->addObj(m_qRoot, obj);
			}
			else if(root->ListObj[i]->m_brelease == true)
				root->ListObj.erase(root->ListObj.begin() + i);
			else
				result.push_back(root->ListObj[i]);
		}
	}
	
	//check Left Top
	if(root->LT != NULL && IntersectRect( &rec, root->LT->m_Rect, &Screen)!= 0 )
		getObjInRect(root->LT, Screen, result);
	//check Right top
	if(root->RT != NULL && IntersectRect( &rec, root->RT->m_Rect, &Screen)!= 0)
		getObjInRect(root->RT, Screen, result);
	//check left bottom
	if(root->LB != NULL && IntersectRect( &rec, root->LB->m_Rect, &Screen)!= 0)
		getObjInRect(root->LB, Screen, result);
	//check right bottom
	if(root->RB != NULL && IntersectRect( &rec, &Screen, root->RB->m_Rect )!= 0)
		getObjInRect(root->RB, Screen, result);
}

void CQuadTree::getAllObj(QuadNode* root, vector<Object*> &result)
{
	for( int i = 0; i < root->ListObj.size(); i++)
	{
		result.push_back(root->ListObj[i]);
	}

	if(root->LT != NULL)
		getAllObj(root->LT, result);
	if(root->RT != NULL)
		getAllObj(root->RT, result);
	if(root->LB != NULL)
		getAllObj(root->LB, result);
	if(root->RB != NULL)
		getAllObj(root->RB, result);
}

void CQuadTree::updateObject(RECT _Screen, int DeltaTime, int moveCame)
{
	vector<Object*> result;
	//get object
	getObjInRect(m_qRoot, _Screen, result);
	//getAllObj(m_qRoot, result);

	for (int i = 0; i < result.size(); i++)
	{
		result[i]->update(DeltaTime, moveCame);
	}
}

void CQuadTree::drawObj(RECT _Screen)
{
	vector<Object*> result;
	//get object
	getObjInRect(m_qRoot, _Screen, result);
	//getAllObj(m_qRoot, result);

	for (int i = 0; i < result.size(); i++)
	{
		result[i]->render();
	}

}

Object* CQuadTree::checkCollision(QuadNode* root, RECT r, int seq)
{
	RECT rec;
	for (int i = 0; i < root->ListObj.size(); i++)
	{
		//Check Collision if n is 0 then haven't collision

		if(root->ListObj[i]->m_nId != 1 && IntersectRect( &rec, root->ListObj[i]->m_ObRect, &r) != 0 && root->ListObj[i]->m_bcheckDie !=true)
		{
			return root->ListObj[i];
		}
	}
	//LT
	if (root->LT != NULL && IntersectRect( &rec, root->LT->m_Rect, &r)!= 0 )
	{
		Object *ob = checkCollision(root->LT, r, seq);
		if(ob != NULL)
			return ob;
	}
	//RT
	if (root->RT != NULL && IntersectRect( &rec, root->RT->m_Rect, &r)!= 0)
	{
		Object *ob = checkCollision(root->RT, r, seq);
		if(ob != NULL)
			return ob;
	}
	//LB
	if (root->LB != NULL && IntersectRect( &rec, root->LB->m_Rect, &r)!= 0)
	{
		Object *ob = checkCollision(root->LB, r, seq);
		if(ob != NULL)
			return ob;
	}
	//RB
	if (root->RB != NULL && IntersectRect( &rec, root->RB->m_Rect, &r)!= 0)
	{
		Object *ob = checkCollision(root->RB, r, seq);
		if(ob != NULL)
			return ob;
	}
	//
	return NULL;
}

void CQuadTree::checkCollision(QuadNode* root, RECT r, int seq, vector<Object*>& result)
{
	RECT rec;
	for (int i = 0; i < root->ListObj.size(); i++)
		if(root->ListObj[i]->m_checkDie == false && IntersectRect( &rec, root->ListObj[i]->m_ObRect, &r)!= 0)
			result.push_back(root->ListObj[i]);

	//LT
	if (root->LT != NULL && IntersectRect( &rec, root->LT->m_Rect, &r)!= 0)
	{
		checkCollision(root->LT, r, seq, result);
	}
	//RT
	if (root->RT != NULL && IntersectRect( &rec, root->RT->m_Rect, &r)!= 0)
	{
		checkCollision(root->RT, r, seq, result);
	}
	//LB
	if (root->LB != NULL && IntersectRect( &rec, root->LB->m_Rect, &r)!= 0)
	{
		checkCollision(root->LB, r, seq, result);
	}
	//RB
	if (root->RB != NULL && IntersectRect( &rec, root->RB->m_Rect, &r)!= 0)
	{
		checkCollision(root->RB, r, seq, result);
	}
}

void CQuadTree::removeAll(QuadNode *root)
{
	if(root != NULL)
		root->ListObj.clear();

	if(root->LT != NULL)
		removeAll(root->LT);
	if(root->RT != NULL)
		removeAll(root->RT);
	if(root->LB != NULL)
		removeAll(root->LB);
	if(root->RB != NULL)
		removeAll(root->RB);
}